/*
 * @FilePath: /data-and-structure-lv/02/binarysearch/find-sum.c
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-12-12 16:39:29
 * @Author: zsk
 * @Copyright: open source
 * @LastEditors: zsk
 * @LastEditTime: 2021-12-12 17:29:38
 */
#include <stdio.h>

typedef int ElementType;

int binarysearch_first_smaller_or_eq_index(ElementType *a, ElementType key, int length, int p, int r)
{
    if (p > r)
    {
        return -1;
    }
    else if (p == r)
    {
        if (key <= a[p])
        {
            return p;
        }
        else if (p < length - 2)
        {
            return p + 1;
        }
        return length - 1;
    }

    int mid = (p + r) / 2;
    if (key < a[mid])
    {
        binary_search(a, key, p, mid - 1);
    }
    else if (key > a[mid])
    {
        binary_search(a, key, mid + 1, r);
    }
    else if (key == a[mid])
    {
        return mid > 1 ? mid - 1 : 0;
    }
}

int binary_search(ElementType *a, ElementType key, int p, int r)
{
    if (p > r)
    {
        return -1;
    }

    int mid = (p + r) / 2;
    if (key < a[mid])
    {
        binary_search(a, key, p, mid - 1);
    }
    else if (key > a[mid])
    {
        binary_search(a, key, mid + 1, r);
    }
    else if (key == a[mid])
    {
        return mid;
    }
}

void find_sum(ElementType *a, ElementType key, int length, int p, int r)
{
    int q = binarysearch_first_smaller_or_eq_index(a, key, length, p, r);
    int p2 = binarysearch_first_smaller_or_eq_index(a, key / 2, length, p, r);
    for (int i = q; i >= p2; i--)
    {
        ElementType sub_key = key - a[i];
        int index = binary_search(a, sub_key, p, q);
        if (index != -1 && index != i)
        {
            printf("[%d,%d] ", a[index], a[i]);
        }
    }
    printf("\n");
}

void main()
{
    ElementType a[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int length = 8;
    int index = binarysearch_first_smaller_or_eq_index(a, 6, length, 0, 7);
    printf("index: %d\n", index);

    find_sum(a, 6, length, 0, length - 1);

    ElementType b[] = {1, 2, 3, 4, 5, 7, 8, 9};
    find_sum(b, 9, length, 0, length - 1);
}